package com.tgy.algorithm.base01._排序;

import com.tgy.algorithm.sort.QuickSort01;

import java.util.Arrays;

public class _插入排序 {

    public static void insertSort(int[] nums) {

        if (nums == null || nums.length == 0 || nums.length == 1) {
            return;
        }

        int len = nums.length;

        for (int i = 1; i < len; i++) {

            int index = findGT(nums,i);
            if (index != -1) {
                int value = nums[i];
                int idx = i;
                while (idx > index) {
                    nums[idx] = nums[idx - 1];
                    idx--;
                }
                nums[index] = value;
            }
        }
    }

    public static int findGT(int[] nums,int index) {

        int retIndex = -1;
        int value = nums[index];
        int leftIndex = 0;
        int rightIndex = index - 1;

        while (leftIndex <= rightIndex) {
            int mid = leftIndex + ((rightIndex  - leftIndex) >> 1);
            if (nums[mid] > value) {
                retIndex = mid;
                rightIndex = mid - 1;
            }else {
                leftIndex = mid + 1;
            }
        }

        return retIndex;
    }

    public static int[] randomArr(int maxValue,int maxLen) {
        int len = (int) (Math.random() * (maxLen + 1));
        int[] ints = new int[len];
        for (int i = 0; i < len; i++) {
            ints[i] = (int) (Math.random() * (maxValue + 1) - Math.random()*maxValue);
        }

        return ints;
    }


    public static boolean arrayEqual(int[] orgs, int[] dests) {

        if (orgs == null || dests == null) {
            return false;
        }

        if (orgs == dests) {
            return true;
        }

        int orgLen = orgs.length;
        int destLen = dests.length;

        if (orgLen != destLen) {
            return false;
        }

        for (int i = 0; i < orgLen; i++) {
            if (orgs[i] != dests[i]) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {

//        int[] nums = new int[]{2,3,1,4,8,5,3};
//        insertSort(nums);
//        System.out.println(Arrays.toString(nums));
        int maxValue = 100;
        int maxLen = 40;
        int count = 1000000;
        for (int i = 0; i < count; i++) {

            int[] ints = randomArr(maxValue, maxLen);
            int[] ints1 = Arrays.copyOf(ints, ints.length);
            int[] ints2 = Arrays.copyOf(ints, ints.length);
            Arrays.sort(ints2);
//            insertSort(ints1);
            QuickSort01.quickSort(ints1);
            if (!arrayEqual(ints1,ints2)) {
                System.out.println("fucking");
                System.out.println(Arrays.toString(ints));
                break;
            }else {
//                System.out.println(Arrays.toString(ints));
//                System.out.println(Arrays.toString(ints1));
            }
        }
    }
}
